package midalgorithms.arrandstr;

public class _06IncreasingTriplet {
    public static boolean increasingTriplet(int[] nums) {
        int len = nums.length;
        if (len < 3){
            return false;
        }
        /**
         * 时间复杂度O(n2)
         * 运行大数组时超时
        int min = 0,mid;
        for (int i = 0;i < len;i++){
            if (nums[i] > nums[min]){
                mid = i;
                //  只要在后面的序列中找一个比nums[mid]大的就行了
                for (int j = i+1;j < len;j++){
                    if (nums[j] > nums[mid]){
                        return true;
                    }
                }
            }else {
                min = i;
            }
        }
        return false;
        */
        //  贪心算法
        /**
         * 1、如果 \textit{num} > \textit{second}num>second，则找到了一个递增的三元子序列，返回 \text{true}true；
         * 2、否则，如果 \textit{num} > \textit{first}num>first，则将 \textit{second}second 的值更新为 \textit{num}num；
         * 3、否则，将 \textit{first}first 的值更新为 \textit{num}num。
         */
        int min = nums[0],mid = Integer.MAX_VALUE;
        for (int i = 1;i < len;i++){
            if (nums[i] > mid){
                return true;
            }else {
                if (nums[i] > min){
                    mid = nums[i];
                }else {
                    min = nums[i];
                }
            }
        }
        return false;
    }
}
